package 链表和树.二叉树;

import javax.swing.tree.TreeNode;

//Java：平衡二叉树
public class BalancedBinaryTree{
    public static void main(String[] args) {
        Solution solution = new BalancedBinaryTree().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
//    public class TreeNode {
//        int val;
//        TreeNode left;
//        TreeNode right;
//        TreeNode() {}
//        TreeNode(int val) { this.val = val; }
//        TreeNode(int val, TreeNode left, TreeNode right) {
//            this.val = val;
//            this.left = left;
//            this.right = right;
//        }
//    }
class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != 1;
    }

    private int getHeight(TreeNode node){
        if(node == null){
            return 0;
        }

        int LH = getHeight(node.left);
        int RH = getHeight(node.right);
        //进行拦截判断
        if(LH == -1 || RH == -1 || Math.abs(LH - RH) > 1){//Math.abs(LH - RH) > 1第一次出现 -1 的地方
            //后续不会再进行递归而是不断将-1传递到父节点最后到根节点进行判断
            return -1;//LH == -1 || RH == -1
        }

        return Math.max(LH, RH) +1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}